#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "HashTable.h"


typedef unsigned short KeyType;// 设关键字域为整型

/* element of the hash table's chain list */
struct kv
{
    struct kv   * next;
    KeyType     key;
    void        * value;
    void        (*free_value)( void* );
};

/* constructor of struct kv */
static void init_kv( struct kv* kv )
{
    kv->next    = NULL;
    kv->key     = 0;
    kv->value   = NULL;
    kv->free_value  = NULL;
}


/* destructor of struct kv */
static void free_kv( struct kv* kv )
{
    if ( kv )
    {
        if ( kv->free_value )
        {
            kv->free_value( kv->value );
        }
        kv->key = 0;
        system_free( kv );
    }
}



static KeyType hash( KeyType key ,int table_size)
{
    return(key%table_size);
}

// static unsigned int hash_33( char* key )
// {
//  unsigned int hash = 0;
//  while ( *key )
//  {
//      hash = (hash << 5) + hash + *key++;
//  }
//  return(hash);
// }


/* new a HashTable instance */
HashTable* hash_table_new(int tableSize)
{
    HashTable* ht = system_malloc( sizeof(HashTable) );
    if ( NULL == ht )
    {
        hash_table_delete( ht );
        return(NULL);
    }
    ht->table = system_malloc( sizeof(struct kv*) * tableSize );
    ht->table_size = tableSize;
    if ( NULL == ht->table )
    {
        hash_table_delete( ht );
        return(NULL);
    }
    memset( ht->table, 0, sizeof(struct kv*) * tableSize );

    return(ht);
}


/* delete a HashTable instance */
void hash_table_delete( HashTable* ht )
{
    if ( ht )
    {
        if ( ht->table )
        {
            int i = 0;
            for ( i = 0; i < ht->table_size; i++ )
            {
                struct kv   * p = ht->table[i];
                struct kv   * q = NULL;
                while ( p )
                {
                    q = p->next;
                    free_kv( p );
                    p = q;
                }
            }
            system_free( ht->table );
            ht->table = NULL;
        }
        system_free( ht );
    }
}


/* insert or update a value indexed by key */
int hash_table_put2( HashTable* ht, KeyType key, void* value, void (*free_value)( void* ) )
{
    int     i   = hash( key ,ht->table_size );
    struct kv   * p = ht->table[i];
    struct kv   * prep  = p;

    while ( p ) /* if key is already stroed, update its value */
    {
        if ( p->key == key )
        {
            if ( p->free_value )
            {
                p->free_value( p->value );
            }
            p->value    = value;
            p->free_value   = free_value;
            break;
        }
        prep    = p;
        p   = p->next;
    }

    if ( p == NULL ) /* if key has not been stored, then add it */
    {
        struct kv * kv = system_malloc( sizeof(struct kv) );
        if ( NULL == kv )
        {
            return(-1);
        }
        init_kv( kv );
        kv->next = NULL;
        kv->key     = key;
        kv->value   = value;
        kv->free_value  = free_value;

        if ( prep == NULL )
        {
            ht->table[i] = kv;
        }else  {
            prep->next = kv;
        }
    }
    return(0);
}


/* get a value indexed by key */
void* hash_table_get( HashTable* ht, KeyType key )
{
    int     i   = hash( key ,ht->table_size );
    struct kv   * p = ht->table[i];
    while ( p )
    {
        if ( p->key == key )
        {
            return(p->value);
        }
        p = p->next;
    }
    return(NULL);
}


/* remove a value indexed by key */
void hash_table_rm( HashTable* ht, KeyType key )
{
    int i = hash( key ,ht->table_size );

    struct kv   * p = ht->table[i];
    struct kv   * prep  = p;

    while ( p )
    {
        if ( p->key == key )
        {
            //free_kv( p );
            if ( p == prep )
            {
                ht->table[i] = p->next;
            }else  {
                prep->next = p->next;
            }
            break;
        }
        prep    = p;
        p   = p->next;
    }
    if(p != NULL)
        free_kv( p );
}


int hash_table_traversal(HashTable* ht,void (*callback)( void* ))
{
    struct kv   * p = NULL;
    struct kv   * pNext = NULL;
    int i = 0;
    int icnt = 0;

    for(i = 0 ; i < ht->table_size ; i++)
    {
        p = ht->table[i];
        if(p != NULL)
        {
            while(p != NULL)
            {
                icnt++;
                pNext = p->next;
                callback(p->value);//p maybe system_free
                p = pNext;
            }
        }
    }
    return icnt;
}



